The invention relates to techniques that obtain performance of combinations of actions, such as coordination or scheduling techniques.
Various techniques have been proposed for coordinating and scheduling actions.
Andreoli, J.-M., Pacull, F., Pagani, D., and Pareschi, R., xe2x80x9cMultiparty Negotiation of Dynamic Distributed Object Servicesxe2x80x9d, Journal of Science of Computer Programming, Vol. 31, 1998, pp. 179-203, describe Coordination Language Facility (CLF), a programming framework that extends object-oriented programming (OOP) with constructs that support dynamic services and multi-service coordination. CLF merges OOP with transaction systems that coordinate access to distributed resources, enabling coordination of multiple, distributed objects. A client object can communicate with multiple servers to negotiate consensus over a set of services that match complex criteria and to concurrently execute the services on each server while respecting consistency of global execution.
Andreoli et al. describe a set of CLF operations that support a negotiation dialogue between several server objects through a client object, where the client calls for and collects offers for various services it wants to combine in some constrained way, before deciding for one combination obtained by selecting one offer from each service. Another set of CLF operations support an elementary transaction mechanism so that a set of actions from different servers can be performed atomically; the client proceeds in two phases, first reserving each of the actions separately, and then proceeding based on the responses to reservationsxe2x80x94if all are accepted, the client confirms them, but if one returns a hard rejection, the client cancels any that have been accepted and abandons the transaction, and if one returns a soft rejection, the client cancels any that have been accepted and defers the transaction unless a hard rejection has also been received.
As described by Andreoli et al., the CLF object model provides a straightforward model of coordination in which a primitive coordination action consists of atomic removal of a number of resources from some objects followed by insertion of resources into the same or other objects. The coordination action is specified by a production rule whose left-hand side lists properties of resources to be removed and whose right-hand side lists properties of resources to be inserted, each property being tagged with an identifier of a CLF object implementing the property. A coordinator continuously attempts to apply rules whenever they are active, following an adaptation of production rule engine algorithms: A search engine retrieves active rules and finds instantiations for their left-hand sides; a transaction engine attempts to consume atomically the left-hand side of rules for which the search engine has found a complete instantiation and insert their right-hand side; and surrogates handle communications with remote servers.
The invention addresses a problem that arises in performing coordination using both search techniques and transaction techniques, such as with the search engine and transaction engine described in the Andreoli et al. article discussed above. Although the transaction engine described by Andreoli et al. atomically consumes the left-hand side of rules for which the search engine has found a complete instantiation, no specific technique is disclosed for passing information between the search engine and the transaction engine to make this possible. In practice, bottlenecks can develop as the number of offers received increases.
The invention alleviates this problem by providing a technique in which each offer indicates an identifier of an action that is offered. The technique obtains combination data indicating a combination of two or more action types and generates one or more combinations of offers, where the offers in each combination together are offering the indicated combination. In generating combinations of offers, the technique provides inquiries to sources, with each inquiry requesting offers that offer to perform actions of one of the action types and that each indicate an action identifier. The technique then uses the action identifiers from any of the generated combinations to obtain performance.
The technique thus provides an elegant way to collect data that a search technique can use to generate a combination of offers, data that a transaction technique can also use to obtain performance of each action. As a result, the technique can be used to simply yet effectively integrate search and transaction techniques.
The sources of actions can be servers, and the combination data can indicate a service identifier for each action type, identifying a service that can be performed by a server to provide an instance of the action type. The servers can be accessible through a network, and can perform services by executing instructions, so that the method can coordinate distributed software actions.
The combination of action types can be a conjunction, and the method can associate action identifiers from offers with service identifiers from the combination data, thus generating a combination of offers. The method can determine whether all service identifiers have associated action identifiers, thus determining whether the offers in a generated combination together are offering the combination of action types indicated by the combination data.
The combination data can also indicate a set of variable identifiers for each service identifier, with each variable identifier identifying a variable that is applicable to the service identified by the service identifier. The sets of variable identifiers for first and second service identifiers can both include one or more shared variable identifiers identifying shared variables applicable to both. The method can provide a first inquiry to servers that can perform the first service, indicating the first service with the shared variable unspecified and requesting offers that offer to perform the first service. After receiving at least one offer in response to the first inquiry, offering to perform the first service with a specified value of the shared variable, the method can provide a second inquiry to servers that can perform the second service. The second inquiry can indicate the second service with the specified value of the shared variable from one of the offers and can request offers that offer to perform the second service with the specified value of the shared variable.
Where the combination is a conjunction, the method can also provide a reserve request to the source of each offer in the generated combination of offers, indicating the offer""s action identifier and requesting a return communication indicating whether the offer is available and reserved. If all the offers in the generated combination are available and reserved, the method can provide a perform request to the source of each offer, indicating the offers action identifier and requesting performance. The reserve request can also indicate a requester identifier and request that the source reserve the action for the identified requester.
The technique can also be implemented in a system with processing circuitry and connecting circuitry for connecting the processing circuitry to sources of action. The processing circuitry can obtain combination data, can generate one or more combinations of offers, and can use action identifiers to obtain performance, generally as described above. The connecting circuitry can, for example, connect the processing circuitry to the Internet.
The system can also include memory circuitry storing instruction data defining instructions the processing circuitry can execute. The processing circuitry can execute search engine instructions to generate the combinations of offers and can execute transaction engine instructions to use the action identifiers to obtain performance.
Memory circuitry can also store a set of service combination data items, each indicating a combination of service identifiers that could be an instance of the combination of action types indicated by the combination data. The processing circuitry can update the set of service combination data items by associating action identifiers from offer signals with service identifiers. The processing circuitry can use the set of service combination data items in determining whether all service identifiers have associated action identifiers.
Memory circuitry can also store a set of trigger data items, each indicating an offer received in response to an inquiry. The processing circuitry can create a new service combination data item for a trigger data item, with the action identifier from the trigger data item associated with the service identifier indicated by the inquiry.
Memory circuitry can also store a set of invalid action data items. After using action identifiers to obtain performance, the processing circuitry can create an invalid action data item indicating each action identifier that was used. The processing circuitry can use the action identifier indicated by each invalid action data item to remove service combination data items having service identifiers associated with the same action identifier.
The technique can also be implemented in an article of manufacture with a storage medium and instruction data on the storage medium. The instruction data define a sequence of instructions that a processor can access using a storage medium access device. In executing the sequence of instructions, the processor can obtain combination data, can generate one or more combinations of offers, and can use action identifiers to obtain performance, generally as described above.
The new technique can also be implemented in a method that operates a first machine to transfer data to a second machine over a network, where the transferred data includes instruction data as described above.
In comparison with the technique described in the Andreoli et al. article, the new technique is advantageous because it can be used to pass information between search engine and transaction engine in a way that prevents bottlenecks. Actions, represented by their action identifiers, can be manipulated and passed around in various ways by simple interactions between search and transaction engines. Examples of manipulations include reserving, confirming, canceling, and checking of actions. As a result, search and transaction phases can continue in parallel with a pipeline of combinations passing between them.
The new technique is also advantageous because it can be implemented in a manner that permits interdependent search branches. For example, an offer received in response to an inquiry can then be used to provide a more fully specified inquiry, and so forth, which can target the search toward the parts of the search space that are consistent with existing offers and that are therefore most likely to contain available combinations of offers. In a simple example of trip planning, an offer of a room in a specific hotel can be used to provide an inquiry signal requesting offers of other services that are near the hotel, such as restaurants or car rentals.
The new technique is also advantageous because it can be extended to enable retroaction from transaction engine to search engine so that search trees can be pruned to enhance overall performance. Whenever, in the transaction phase, reservation of an action fails irretrievably, the search phase can use this information to cut branches of the search that depend on the action for which reservation failed. This is appropriate because any development of these branches would attempt the same failed reservation and would therefore inevitably fail.
The new technique is also advantageous because it can address two major sources of complexity for the coordination of software activities in an open world. One source of complexity is choices. In an open world, a service may be performed in different ways or at different conditions, from which a client must choose, possibly non-deterministically. The set of choices for a given service may never be closed, because new choices may arise dynamically due to changes in other parts of an application. Another source of complexity is conflicts. In an open world, resource conflicts among services executed concurrently may not be anticipated. To avoid inconsistencies in case of conflict, one of the conflicting services must abort in order to satisfy the other.
The new technique can be used to combine component software services, each of which is individually capable of generating choices for its service invocations and of dealing with conflicts in its service execution. The new technique can generate combinations of services, sometimes referred to as xe2x80x9ccoordination blocksxe2x80x9d, that exploit the choice and conflict management capabilities of the component services in order to achieve a coordinated behavior.
For example, the new technique can alleviate complexity resulting from choices by using search techniques that try all the combinations of choices generated without exclusion. Further, the technique can be applied when choices are interdependent, as in the case of a multi-party negotiation of services.
Similarly, the new technique can alleviate complexity resulting from conflicts by ensuring that, whenever an execution is aborted within a coordination block due to a conflict, the whole block is aborted. Further, the new technique can distinguish between temporary (soft) conflicts and permanent (hard) conflicts.